//
// Created by ASUS on 2022/5/31.
//
#include "stdio.h"
/*待排序的数组元素的编号从0开始到num_elements-1。
要求：
1.实现如下  声明的insertion_sort函数。
2.在把从1到num_elements-1位置上的每个元素放置到合适位置  上之后，将此时unso  rted_array里的全部元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出 之后换行。比如输入的unsorted_array数组里依次包含4个元素4, 3, 2, 1。那么输出的内容应该如下：
3 4 2 1
2 3 4 1
1 2 3 4

*/
void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void insertion_sort(int unsorted_array[], int num_elements){
    int i,j,temp;
    for(i=1 ; i < num_elements;i++){
        if(unsorted_array[i-1]>unsorted_array[i]){
            temp = unsorted_array[i];
            for ( j = i-1; unsorted_array[j] > temp && j != -1; --j) {
                unsorted_array[j+1] = unsorted_array[j];
            }
            unsorted_array[j+1] = temp;
        }
        print_array(unsorted_array,num_elements);
    }
}
/*待排序的数组元素的编号从0开始到total_num_elements-1。
要求：
1.实现如下声明  的partition函数；永远选择low位置上的元素作为pivot支撑元素；在partition函数返回pivot支撑元素的位置之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出 之后换行。
2.递归实现如下声明的quick_sort函数；在每次递归时先处理左侧的子数组，再处理右侧的子数组；quick_sort必须调用partition函数获取pivot支撑元素的位置。
3.比如当输入的unsorted_array数组的元素依次为 3, 1, 2, 5, 4时，输出应该为：
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5

*/
int partition(int L[], int low,  int  high, int total_num_elements){
    int pivot =L[low];
    int temp;
    while (low<high){
        while (low < high&& L[high] >= pivot){
            high--;
        }
        temp = L[low];
        L[low] = L[high];
        L[high] = temp;
        while (low <high && L[low] <= pivot ){
            low++;
        }
        temp = L[low];
        L[low] = L[high];
        L[high] = temp;
    }
    pivot = low;
    print_array(L,total_num_elements);
    return pivot;
};
void QSort(int L[], int low,  int  high, int total_num_elements){
    int pivot;
    if (low<high){
        pivot = partition(L,low,high,total_num_elements);
        QSort(L,low,pivot-1,total_num_elements);
        QSort(L,pivot+1,high,total_num_elements);
    }
}
/*
待排序的数组元素的编号从0开始到num_elements-1
要求：
1.实现如下声明的heap_sort函数。
2.在每次对已经建好的最大堆进行调整然后把当前根里的最大值放置到合适正确的位置之后、再次调整形成最大堆之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出之后换行。例如：
10 60 12 40 30 8 70
8 40 12 10 30 60 70
8 30 12 10 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
*/

void AdjustMaxHeap(int N[], int target, int n) {
    int i = target;
    int j = 2 * i + 1;
    int temp = N[i];
    while(j <= n) {
        if(j < n && N[j] < N[j + 1]) {	// 找出左右孩子的最大值
            j++;
        }
        if(temp < N[j]) {	// 不满足大根堆则交换元素值
            N[i] = N[j];
            i = j;
            j = 2 * j + 1;
        }
        else {
            break;
        }
    }
    N[i] = temp;
}
void heap_sort(int unsorted_array[], int num_elements){
    int i;
    // 构造大根堆，元素从 0 开始
    for(i = num_elements/2 - 1; i >=0; i--) {
        AdjustMaxHeap(unsorted_array, i, num_elements - 1);
    }
    int temp;
    // 取堆顶元素，重新构造新堆
    for(i = num_elements - 1; i > 0; i--) {
        temp = unsorted_array[0];
        unsorted_array[0] = unsorted_array[i];
        unsorted_array[i] = temp;
        print_array(unsorted_array,num_elements);
        AdjustMaxHeap(unsorted_array, 0, i - 1);
    }
}
int main(){
    int a[7]  = {10,60,12,40,30,8,70};
    int size = 7;
    heap_sort(a,size);
}

